这道题一看就是一道强连通分量的题，不会的可以参考我的博客。
当我们用缩点之后，记新图点的个数为。我们枚举原图的每一条边，计算新图中的点的出度。对于点，我们把它的出度记为。那么，会有以下几种情况：
1.没有一个为0，说明每一个点至少有一条连向其他边的有向边，那么新图至少有条边，一定会有一个环(因为条边是一棵树，无论如何加边都会构成环)，但缩点后不可能有环，矛盾。
CF794F Leha and security system
一道神奇的线段树...
题目要求区间修改，区间查询，很容易想到线段树，但是怎么维护每一位数字呢？
显然，我们将每位拆分，对于每一个数字维护他的贡献，如 1221123 中 1 的贡献为 1001100 , 2 的贡献为 110010。于是，我们需要10棵线段树，维护0−9的贡献。
CF480E Parking Lot
显然，如果每次删一个点，答案可能会减小，而且你还不知道在哪里减小的...
所以我们反向思考，如果每次加一个点，那么答案肯定是不减的，而且如果答案变大，新矩阵一定包含该点。
up[i][j]表示以(i,j)为起点出发向上能到达的 ′. ′ 的个数。（遇到 ′X ′ 停止）
P3831 [SHOI2012]回家的路
这道题显然是最短路，但是似乎转向时不好处理，于是我们要用到分层图。
实现很简单，建立两层图，第一层记录横向边，第二层记录纵向边，相同的关键点两层图连一条费用为1的边。
还有，这道题只需要在关键点之间连边（非关键点无法转向，连了也没用），路径长度为坐标差*2。
P4400 [JSOI2008]Blue Mary的旅行
这道题貌似很多人用的是网络流+分层图。这里介绍一种费用流解法。
可以证明，最后一个人到达的时间是小于第100天的。
那么对于每一趟航班，如果他的起点是u，终点为v，可搭乘的人的数量为w。那我们就对(u,v)连100条流量为w,费用为i的边（i表示第几天），分别表示第i天的航班。
0%